studlog

파라메트릭 서치란 최적화 문제를 결정 문제로 바꿔 이분 탐색을 이용해 해결하는 방법이다. 여기서 결정 문제란 예 혹은 아니오 형태의 답이 나오는 문제를 말한다. 예를 들어 외판원 문제를 최적화 문제와 결정 문제로 표현하면 아래와 같다.optimize(G) = 그래프 G의 모든 정점을 한 번씩 방문하고 시작점으로 돌아오는 최단 경로의 길이를 반환한다.decision(G, \(x\)) = 그래프 G의 모든 정점을 한 번씩 방문하고 시작점으로 돌아오는 길이가 \(x\)이상인 경로가 있는 있는가?최적화 문제의 답은 보통 실수, 정수이므로 답의 경우의 수가 무한개이지만, 결정 문제의 답은 예 혹은 아니오 이므로 답의 경우의 수가 2개이다.왜 결정문제로 바꿔서 푸는가?최적화 문제를 결정 문제로 바꾼 후 결정 문제를..

A circular queue can be implemented using array and linked list. To implement a circular queue using a linked list, you must use a circular linked list where the rear node is connected to the front node.Time Complexity AnalysisTime ComplexityEnqueue : \(O(1)\)Dequeue: \(O(1)\)Space Complexity : \(O(n)\) as the queue is size of \(n\)Circular Queue Implementation Using An LinkedList in C++Header I..

A circular queue is an extended version of a regular queue. Unlike a linear queue, the last element of a circular queue connects back to the first element, forming a circular structure. This is useful for efficiently managing fixed-size data buffers.Advantages of Circular QueuesEfficient Space Utilization: The circular nature allows reusing spaces once occupied by dequeued elements, avoiding the..

A doubly linked list is a data structure consisting of nodes, where each node contains three fields:Data: The value or information stored in the node.Prev: A pointer to the previous node in the list.Next: A pointer to the next node in the list.This structure allows traversal in both forward and backward directions, providing greater flexibility compared to a singly linked list.Advantages of Doub..

둘러쌓인 영역 찾기문제점경계와 인접한 영역은 어떻게 필터링할 것인가? 해결 아이디어경계에 있는 'O'에서 BFS를 수행해 경계와 인접한 영역을 찾는다.queue> q;for (int y = 0; y  관련 문제[Leetcode] Surrounded RegionsBFS에서 방문 체크의 상태가 2차원 배열인 경우문제점트리(map, int>)를 사용해 상태를 관리할 경우 메모리 및 시간 초과. 해결 아이디어2차원 배열 상태를 문자열로 변환하여 해시 키 값(unordered_map)으로 사용해 방문 체크를 한다. 관련 문제[BOJ 1525] 퍼즐방문할 수 없는 구역이 있는 경우방문할 수 없는 구역이란?(정점(\(X\), \(Y\))을 기준으로 거리 \(D\) 이하의 정점들의 영역) 해결 아이디어다익스트라 알고리..

퀵소트는 피봇을 정하는 파티션 과정과 2번의 분할 과정으로 이루어져 있다. \(n\)개의 원소를 퀵소트로 정렬하는 데 걸리는 시간을 \(T(n)\)이라 할 때 \(T(n)\)은 \(m\)개와 \(n-m\)개로 분할된 원소를 정렬하는 시간과 \(n\)개의 원소 중 피봇을 정하는 파티션 과정으로 나눌 수 있다. 아래 식을 활용해서 퀵소트의 시간복잡도를 구할 수 있다.$$T(n) = T(m) + T(n-m) + C(n) $$ Best case time complexity퀵소트는 피봇이 항상 배열을 균등하게 분할하여 분할의 횟수가 \(\log n\)번 실행되는 경우에 \(O(n\log n)\)에 동작한다. 최선의 방법으로 퀵소트를 할 때 걸리는 시간을  \(T(n)\)이라고 하면 \(T(n)\)은 아래와 같다...

단조 스택(Monotonic Stack) 이란단조 스택(Monotonic Stack)은 스택(Stack) 자료 구조의 변형 중 한 개로 스택의 원소들이 단조 증가 혹은 단조 감소 상태인 스택을 말한다. 겉보기에는 힙(Heap) 자료구조와 비슷하게 보이지만 다르다. 정확하게 말하자면 단조 스택이란 스택에 원소를 삽입할 때 스택의 상태가 단조 증가 혹은 감소를 유지되는 것을 말한다. 사실 단조 스택은 자주 쓰이지는 않는다. 하지만 특정 문제에서는 단조 스택이 힘을 발휘할 때가 있다. 그중 한 개는 자신보다 처음으로 크거나 작은 원소의 값을 찾는 문제(Next Greater or Smaller Element)이다. 예를 들어 배열 [2, 1, 2, 4, 3]가 주어졌을 때 자신보다 처음으로 큰 원소를 저장하는..

스패닝 트리스패닝 트리란 무향 그래프의 모든 정점을 연결하는 부분 그래프이다. 간선의 개수는 \(V-1\) 개로 트리 구조이다.  그림 1은 7개의 정점을 6개의 간선을 이용해 연결하는 올바른 스패닝 트리이다. 반면에 그림 2는 0-1-2의 정점으로 이루어진 사이클이 있으며 2, 4번 정점은 연결되어 있지 않으므로 스패닝 트리가 아니다.그림 1그림 2최소 스패닝 트리최소 스패닝 트리란 가중치가 있는 무향 그래프의 스패닝 트리 중에서 가중치의 합이 최소인 스패닝 트리이다. 최소 스패닝 트리를 구하는 알고리즘은 크루스칼 알고리즘과 프림 알고리즘이 대표적이다. 크루스칼 알고리즘가중치가 큰 간선과 가중치가 작은 간선 중 어떤 간선이 최소 스패닝 트리에 포함될 가능성이 높을까? 당연히 가중치가 작은 간선이 최소 ..

Single source shortest pathunweighted graph → BFSweighted graph with nonnegative weights → Dijkstraweighted graph with negative weights → Bellman-ford, SPFAdirected acyclic graph → topological sorting용어 정의경로의 길이 : 경로가 지나는 간선의 가중치의 합정점 \(u\)에서 정점 \(v\)의 최단경로 : u에서 v로 가는 경로의 길이가 최소인 경로간선의 완화(edge relaxation) : 정점 \(u\)에서 \(v\)로의 간선에 대해 dist[\(v\)] > dist[\(u\)] + weight(\(u, v\)) 만족하면 dist[\(v\)]를..

그리디 알고리즘(greedy algorithm)그리디 알고리즘은 완전 탐색, 동적 계획법처럼 답을 구하는 과정을 여러 개의 단계로 나누어 답을 만들어가는 과정은 비슷해보인다. 하지만 각 단계에서 가능한 모든 답을 계산하여 전체적으로 가장 좋은 답을 선택하는 것이 아닌,  각 단계에서 가장 좋은 답을 선택하는 점이 완전 탐색, 동적 계획법과 다른 점이다. 예를 들어 외판원 순회 문제에서 동적 계획법은 현재 정점에서 갈 수 있는 정점 중에 전체 거리를 최소화할 수 있는 정점을 고르지만, 그리디 알고리즘은 단순히 현재 정점에서 다음 정점까지의 거리를 최소화하는 정점을 고른다. 그리디 알고리즘은 "답을 도출하는 과정 중 매 순간 최고의 선택을 해서 결과적으로 최적의 해를 도출하자"로 표현할 수 있다. 그런데 매..